package src.array;

public class no35 {
    //搜索插入位置，二分法
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6};
        int target = 5;
        System.out.println(searchInsert(arr, target));

    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;  //左闭右闭区间
        while (left <= right) {  //当left==right，区间[left, right]依然有效,所以用 <=
            int mid = left + (right - left) / 2;  //防止溢出 等同于(left + right)/2，记住这个写法
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        // 四种情况：
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1
        return right + 1;  //比如[1,3,5,6]，target = 7，最终最终right=3，而7应放在arr[4]，所以返回right+1

    }
}
